home *** CD-ROM | disk | FTP | other *** search
/ isnet Internet / Isnet Internet CD.iso / prog / hiz / 09 / 09.exe / adynware.exe / perl / lib / site / DFA / Kleene.pm
Encoding:
Perl POD Document  |  1999-12-28  |  7.9 KB  |  318 lines
  1.  
  2.  
  3. package DFA::Kleene;  #  DFA = Deterministic Finite Automaton
  4.  
  5.  
  6. use strict;
  7. use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS $VERSION
  8.             $number_of_states %alphabet
  9.             %accepting_states @delta
  10.             @words %language);
  11.  
  12. require Exporter;
  13.  
  14. @ISA = qw(Exporter);
  15.  
  16. @EXPORT = qw();
  17.  
  18. @EXPORT_OK = qw(initialize define_accepting_states define_delta kleene example);
  19.  
  20. %EXPORT_TAGS = (all => [@EXPORT_OK]);
  21.  
  22. $VERSION = '1.0';
  23.  
  24. use Carp;
  25.  
  26. sub initialize
  27. {
  28.     croak "Usage: DFA::Kleene::initialize(\$number_of_states,\$alphabet)"
  29.       if (@_ != 2);
  30.  
  31.     my($number,$alpha) = @_;
  32.     my($i,$j,$k);
  33.  
  34.     croak "DFA::Kleene::initialize(): number of states must be > 0"
  35.       if ($number <= 0);
  36.     croak "DFA::Kleene::initialize(): alphabet must comprise at least one character"
  37.       if (length($alpha) == 0);
  38.  
  39.     $number_of_states = $number;
  40.  
  41.     undef %alphabet;
  42.     undef %accepting_states;
  43.     undef @delta;
  44.     undef @words;
  45.     undef %language;
  46.  
  47.     for ( $i = 0; $i < length($alpha); $i++ )
  48.     {
  49.         $alphabet{substr($alpha,$i,1)} = 1;
  50.     }
  51.  
  52.     for ( $i = 1; $i <= $number_of_states; $i++ )
  53.     {
  54.         $delta[$i] = { };
  55.         $words[$i] = [ ];
  56.         for ( $j = 1; $j <= $number_of_states; $j++ )
  57.         {
  58.             $words[$i][$j] = [ ];
  59.             for ( $k = 0; $k <= $number_of_states; $k++ )
  60.             {
  61.                 $words[$i][$j][$k] = { };
  62.             }
  63.         }
  64.     }
  65. }
  66.  
  67. sub define_accepting_states
  68. {
  69.     croak "Usage: DFA::Kleene::define_accepting_states(\@accepting_states)"
  70.       if (@_ < 1);
  71.  
  72.     my(@final) = @_;
  73.     my($state);
  74.  
  75.     undef %accepting_states;
  76.     foreach $state (@final)
  77.     {
  78.         croak "DFA::Kleene::define_accepting_states(): state $state not in [1..$number_of_states]"
  79.           if (($state < 1) || ($state > $number_of_states));
  80.         $accepting_states{$state} = 1;
  81.     }
  82. }
  83.  
  84. sub define_delta
  85. {
  86.     croak "Usage: DFA::Kleene::define_delta(\$state1,\$character,\$state2)"
  87.       if (@_ != 3);
  88.  
  89.     my($state1,$character,$state2) = @_;
  90.  
  91.     croak "DFA::Kleene::define_delta(): state $state1 not in [1..$number_of_states]"
  92.       if (($state1 < 1) || ($state1 > $number_of_states));
  93.     croak "DFA::Kleene::define_delta(): state $state2 not in [1..$number_of_states]"
  94.       if (($state2 < 1) || ($state2 > $number_of_states));
  95.     croak "DFA::Kleene::define_delta(): only single character or empty string permitted"
  96.       if (length($character) > 1);
  97.     croak "DFA::Kleene::define_delta(): character is not contained in alphabet"
  98.       if ($character && !($alphabet{$character}));
  99.     croak "DFA::Kleene::define_delta(): \$delta[$state1]{'$character'} already defined"
  100.       if (defined $delta[$state1]{$character});
  101.  
  102.     $delta[$state1]{$character} = $state2;
  103. }
  104.  
  105. sub kleene
  106. {
  107.     croak "Usage: DFA::Kleene::kleene()"
  108.       if (@_ != 0);
  109.  
  110.     my($i,$j,$k);
  111.     my($state,$word,$word1,$word2,$word3);
  112.  
  113.     for ( $i = 1; $i <= $number_of_states; $i++ )
  114.     {
  115.         for ( $j = 1; $j <= $number_of_states; $j++ )
  116.         {
  117.             foreach $_ (keys %{$delta[$i]})
  118.             {
  119.                 if ($delta[$i]{$_} == $j)
  120.                 {
  121.                     $words[$i][$j][0]{$_} = 1;
  122.                 }
  123.             }
  124.             if ($i == $j) { $words[$i][$j][0]{''} = 1; }
  125.         }
  126.     }
  127.  
  128.     for ( $k = 1; $k <= $number_of_states; $k++ )
  129.     {
  130.         for ( $i = 1; $i <= $number_of_states; $i++ )
  131.         {
  132.             for ( $j = 1; $j <= $number_of_states; $j++ )
  133.             {
  134.                 foreach $word (keys %{$words[$i][$j][$k-1]})
  135.                 {
  136.                     $words[$i][$j][$k]{$word} = 1;
  137.                 }
  138.                 foreach $word1 (keys %{$words[$i][$k][$k-1]})
  139.                 {
  140.                     foreach $word2 (keys %{$words[$k][$k][$k-1]})
  141.                     {
  142.                         foreach $word3 (keys %{$words[$k][$j][$k-1]})
  143.                         {
  144.                             if ($word2)
  145.                                 { $word = "${word1}(${word2})*${word3}"; }
  146.                             else
  147.                                 { $word = "${word1}${word3}"; }
  148.                             $words[$i][$j][$k]{$word} = 1;
  149.                         }
  150.                     }
  151.                 }
  152.             }
  153.         }
  154.     }
  155.     undef %language;
  156.     foreach $state (keys %accepting_states)
  157.     {
  158.  
  159.         foreach $word (keys %{$words[1][$state][$number_of_states]})
  160.         {
  161.             $language{$word} = 1;
  162.         }
  163.     }
  164.     return( sort(keys %language) );
  165. }
  166.  
  167. sub example
  168. {
  169.     &initialize(6,"ab");
  170.     &define_accepting_states(2,3,4,5);
  171.     &define_delta(1,'a',4);
  172.     &define_delta(1,'b',6);
  173.     &define_delta(2,'a',2);
  174.     &define_delta(2,'b',5);
  175.     &define_delta(3,'a',6);
  176.     &define_delta(3,'b',3);
  177.     &define_delta(4,'a',2);
  178.     &define_delta(4,'b',5);
  179.     &define_delta(5,'a',4);
  180.     &define_delta(5,'b',3);
  181.     &define_delta(6,'a',6);
  182.     &define_delta(6,'b',6);
  183.  
  184.  
  185.     foreach $_ ( &kleene() )
  186.     {
  187.         print "'$_'\n";
  188.     }
  189. }
  190.  
  191. 1;
  192.  
  193. __END__
  194.  
  195. =head1 NAME
  196.  
  197. DFA::Kleene - Kleene's Algorithm for Deterministic Finite Automata
  198.  
  199. Calculates the "language" (set of words) accepted
  200. (= recognized) by a Deterministic Finite Automaton
  201.  
  202. See L<Math::Kleene(3)> for the theory behind this algorithm!
  203.  
  204. =head1 SYNOPSIS
  205.  
  206. =over 4
  207.  
  208. =item *
  209.  
  210. C<use DFA::Kleene qw(initialize define_accepting_states>
  211. C<define_delta kleene example);>
  212.  
  213. =item *
  214.  
  215. C<use DFA::Kleene qw(:all);>
  216.  
  217. =item *
  218.  
  219. C<&initialize(6,"ab");>
  220.  
  221. Define the number of states (state #1 is the "start" state!) of your
  222. Deterministic Finite Automaton and the alphabet used (as a string
  223. containing all characters which are part of the alphabet).
  224.  
  225. =item *
  226.  
  227. C<&define_accepting_states(2,3,4,5);>
  228.  
  229. Define which states are "accepting states" in your Deterministic Finite
  230. Automaton (list of state numbers).
  231.  
  232. =item *
  233.  
  234. C<&define_delta(1,'a',4);>
  235.  
  236. Define the state transition function "delta" (arguments are: "from" state,
  237. character (or empty string!) read during the transition, "to" state).
  238.  
  239. You need several calls to this function in order to build a complete
  240. transition table describing your Deterministic Finite Automaton.
  241.  
  242. =item *
  243.  
  244. C<@language = &kleene();>
  245.  
  246. Returns a (sorted) list of regular expressions describing the language
  247. (= set of patterns) recognized ("accepted") by your Deterministic Finite
  248. Automaton.
  249.  
  250. =item *
  251.  
  252. C<&example();>
  253.  
  254. Calculates the language of a sample Deterministic Finite Automaton.
  255.  
  256. Prints a (sorted) list of regular expressions which should be equivalent
  257. to the following regular expression:
  258.  
  259.             (a(a)*b)*a(a)*(b)*
  260.  
  261. This is the same as
  262.  
  263.             ((a+)b)*(a+)b*
  264.  
  265. =back
  266.  
  267. =head1 DESCRIPTION
  268.  
  269. The routines in this module allow you to define a Deterministic Finite
  270. Automaton and to compute the "language" (set of "words" or "patterns")
  271. accepted (= recognized) by it.
  272.  
  273. Actually, a list of regular expressions is generated which describe the
  274. same language (set of patterns) as the one accepted by your Deterministic
  275. Finite Automaton.
  276.  
  277. The output generated by this module can easily be modified to produce
  278. Perl-style regular expressions which can actually be used to recognize
  279. words (= patterns) contained in the language defined by your Deterministic
  280. Finite Automaton.
  281.  
  282. Other modules in this series (variants of Kleene's algorithm):
  283.  
  284. =over 4
  285.  
  286. =item *
  287.  
  288. Math::MatrixBool (see "Kleene()")
  289.  
  290. =item *
  291.  
  292. Math::MatrixReal (see "kleene()")
  293.  
  294. =back
  295.  
  296. =head1 SEE ALSO
  297.  
  298. Math::MatrixBool(3), Math::MatrixReal(3), Math::Kleene(3),
  299. Set::IntegerRange(3), Set::IntegerFast(3), Bit::Vector(3).
  300.  
  301. =head1 VERSION
  302.  
  303. This man page documents "DFA::Kleene" version 1.0.
  304.  
  305. =head1 AUTHOR
  306.  
  307. Steffen Beyer <sb@sdm.de>.
  308.  
  309. =head1 COPYRIGHT
  310.  
  311. Copyright (c) 1996, 1997 by Steffen Beyer. All rights reserved.
  312.  
  313. =head1 LICENSE
  314.  
  315. This package is free software; you can redistribute it and/or
  316. modify it under the same terms as Perl itself.
  317.  
  318.